package leetcode.f1t100;

/**
 * 旋转后的可重复升序数组查询目标值是否存在
 * https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
 *
 * @author lichx
 * @createTime 2024/1/29 14:07
 */
public class Q81_SearchInRotatedSortedArrayII {

    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length-1, middle;
        while(left<=right){
            middle = (left+right)/2;
            if(nums[middle] == target){
                return true;
            }
            if(nums[left] == nums[middle]){
                left++;
                continue;
            }
            if(nums[left] <= nums[middle]){
                if(nums[left] <= target && target <= nums[middle]) {
                    right = middle -1;
                }else {
                    left = middle + 1;
                }
            }else {
                if(nums[middle] <= target && target <= nums[right]) {
                    left = middle + 1;
                } else {
                    right = middle -1;
                }
            }
        }
        return false;
    }

}
